#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>
// 求数组长度
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
/*
	查找第一个大于等于目标值的元素
	思路：
	1.首先仍然要进行简单二分查找，但是条件要稍微变动一下
	2.如果中间值比目标值小，那说明要去右半区间找，丢弃整个左半区间
	3.如果中间值比目标值大或者相等，那说明找到了一个目标元素，但还需要确定它是不是第一个

	查找最后一个小于等于目标值的元素
	思路：
	1.首先仍然要进行简单二分查找，但是条件要稍微变动一下
	2.如果中间值比目标值大，那说明要去左半区间找，丢弃整个右半区间
	3.如果中间值比目标值小或者相等，那说明找到了一个目标元素，但还需要确定它是不是最后一个
*/

int bs(int arr[], int len, int target) {
	int left = 0, right = len - 1;	// 循环折半的左右区间

	while (left <= right) {	// 只要区间当中还有一个元素,就继续循环二分查找
		int mid = left + (right - left >> 1);
		int diff = arr[mid] - target;
		if (diff < 0) {
			// 循环的去查找右边区间,左半区间丢弃,要改left
			left = mid + 1;
		}
		else
		{
			// 确定找到的目标是不是第一次出现
			if (mid == left || arr[mid - 1] < target) {
				return mid;
			}
			// 不能确定是第一次出现，去左半区间找
			right = mid - 1;
		}
	}
	// 循环都结束了,还没有return 说明目标值不存在
	return -1;
}

int main(void) {
	printf("hello world!\n");
	return 0;
}